import collections
class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        sum_dict = collections.defaultdict(int)
        sum_dict[nums[0]] += 1
        sum_dict[-nums[0]] += 1
        for i in range(1, len(nums)):
            next_dict = collections.defaultdict(int)
            for key in sum_dict:
                next_dict[key + nums[i]] += sum_dict[key]
                next_dict[key - nums[i]] += sum_dict[key]
            sum_dict = next_dict
        return sum_dict[target]




data = Solution()
nums = [0,0,0,0,0,0,0,0,1]
target = 1
print(data.findTargetSumWays(nums, target))
